#ifndef MKAHYPAR_STOP_POLICY_H
#define MKAHYPAR_STOP_POLICY_H
#include "mkahypar/utils/typedef.h"
#include "mkahypar/utils/policy_registry.h"
#include "mkahypar/partition/context.h"

//局部搜索停止策略
namespace mkahypar{
  class StoppingPolicy : public meta::PolicyBase {
  public:
    StoppingPolicy() = default;
  };

  class RandomWalkModel {
  public:
    void resetStatistics() {
      _num_steps = 0;
      _variance = 0.0;
    }

    template <typename Gain>
    void updateStatistics(const Gain gain) {
      ++_num_steps;
      // See Knuth TAOCP vol 2, 3rd edition, page 232 or
      // https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
      if (_num_steps == 1) {
        _MkMinus1 = static_cast<double>(gain);
        _Mk = _MkMinus1;
        _SkMinus1 = 0.0;
      } else {
        _Mk = _MkMinus1 + (gain - _MkMinus1) / _num_steps;
        _Sk = _SkMinus1 + (gain - _MkMinus1) * (gain - _Mk);
        _variance = _Sk / (_num_steps - 1.0);

        // prepare for next iteration:
        _MkMinus1 = _Mk;
        _SkMinus1 = _Sk;
      }
    }

  protected:
    int _num_steps = 0;
    double _variance = 0.0;
    double _Mk = 0.0;  // = mean
    double _MkMinus1 = 0.0;
    double _Sk = 0.0;
    double _SkMinus1 = 0.0;
  };


  class AdvancedRandomWalkModelStopsSearch : public StoppingPolicy,
                                             private RandomWalkModel {
  public:
    bool searchShouldStop(const int, const double beta,
                          const GainType , const GainType) {
      static double factor = (Context::getInstance().adaptive_stopping_alpha / 2.0) - 0.25;
      const bool ret = (_num_steps > beta) &&
                       ((_Mk == 0) || (_num_steps >= (_variance / (_Mk * _Mk)) * factor));
      return ret;
    }
    using RandomWalkModel::resetStatistics;
    using RandomWalkModel::updateStatistics;
  };
}
#endif //MKAHYPAR_STOP_POLICY_H
